GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bipartiter Graph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Bipartiter Graph</h1>

</header>

</div>

Ein bipartiter oder paarer Graph ist ein <a href="Mathematisches_Modell" title="Mathematisches Modell">mathematisches Modell</a> für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von <a href="Zuordnungsproblem" title="Zuordnungsproblem">Zuordnungsproblemen</a>. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Ein <a href="Einfacher_Graph" title="Einfacher Graph">einfacher</a> <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> heißt bipartit oder paar, falls sich seine <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> in zwei <a href="Disjunkt" title="Disjunkt">disjunkte</a> <a href="Teilmenge" title="Teilmenge">Teilmengen</a> A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> verlaufen. Das heißt, für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v,w\}\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v,w\}\in E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83c7ab671f0c5f3d57141f75d5e1403403ad27a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.767ex; height:2.843ex;" alt="{\displaystyle \{v,w\}\in E}" loading="lazy"> gilt entweder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e47413162b1047d7c55dcbef6c81881b64bae37f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.711ex; height:2.176ex;" alt="{\displaystyle v\in A}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c403c519373013be3e8ed9da7900dc23abd012dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.269ex; height:2.176ex;" alt="{\displaystyle w\in B}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/79dc280a10b5e370fa53a66b1e9f362df6e1a606.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.732ex; height:2.176ex;" alt="{\displaystyle v\in B}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/636cdbb131bfc0b5b7ce26222486f074c47ea62e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.248ex; height:2.176ex;" alt="{\displaystyle w\in A}" loading="lazy">. Die Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{A,B\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{A,B\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f71a70f6b5ef10db8ada87f9ea61a03b369918de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.866ex; height:2.843ex;" alt="{\displaystyle \{A,B\}}" loading="lazy"> bezeichnet man dann als Bipartition des Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> und die Mengen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/96c3298ea9aa77c226be56a7d8515baaa517b90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.541ex; height:2.509ex;" alt="{\displaystyle A,B}" loading="lazy"> als Partitionsklassen. Vereinfacht dargestellt, ist ein bipartiter Graph ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a>, in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.

Der <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> heißt vollständig bipartit, falls eine Bipartition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{A,B\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{A,B\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f71a70f6b5ef10db8ada87f9ea61a03b369918de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.866ex; height:2.843ex;" alt="{\displaystyle \{A,B\}}" loading="lazy"> existiert, sodass jeder <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> mit jedem Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> verbunden ist. Einen solchen Graphen bezeichnet man auch als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{m,n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{m,n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/72acfc2cdfe30839be0b076060dcc4d938596b53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.092ex; height:2.843ex;" alt="{\displaystyle K_{m,n}}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> sind. Ein vollständig bipartiter Graph, bei dem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b6100c5ebd48c6fd848709f2be624465203eb173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;" alt="{\displaystyle m=1}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy"> ist, heißt <a href="Sterngraph" title="Sterngraph">Sterngraph</a>.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

Für alle bipartiten Graphen gilt:

<ul><li>Die <a href="Paarungszahl" class="mw-redirect" title="Paarungszahl">Paarungszahl</a> entspricht der <a href="Knoten%C3%BCberdeckungszahl" class="mw-redirect" title="Knotenüberdeckungszahl">Knotenüberdeckungszahl</a>.</li>

<li>Die Partitionsklassen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/96c3298ea9aa77c226be56a7d8515baaa517b90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.541ex; height:2.509ex;" alt="{\displaystyle A,B}" loading="lazy"> sind schon nach Definition <a href="Stabile_Menge" title="Stabile Menge">stabile Mengen</a>.</li>

<li>Der <a href="Chromatischer_Index" class="mw-redirect" title="Chromatischer Index">chromatische Index</a> entspricht seinem <a href="Maximalgrad" class="mw-redirect" title="Maximalgrad">Maximalgrad</a>. Eine gültige Kantenfärbung lässt sich in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6524d6c1f46df6977167a8605414bf7b7d0f8ff1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle O(n\cdot m)}" loading="lazy"> bestimmen.</li>

<li>Jeder bipartite Graph ist <a href="F%C3%A4rbung_(Graphentheorie)#Knotenfärbungen" title="Färbung (Graphentheorie)">2-knotenfärbbar</a>. Jede Partitionsklasse bekommt also eine Farbe zugewiesen. Umgekehrt ist auch jeder 2-färbbare Graph bipartit.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d5595fc0c47452f8fc2aa6e29c3611f047714b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\textstyle k}" loading="lazy">-<a href="Regul%C3%A4rer_Graph" title="Regulärer Graph">regulärer</a> bipartiter Graph besitzt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d5595fc0c47452f8fc2aa6e29c3611f047714b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\textstyle k}" loading="lazy"> disjunkte perfekte <a href="Paarung_(Graphentheorie)" class="mw-redirect" title="Paarung (Graphentheorie)">Matchings</a>.</li>

<li>Ein Graph ist genau dann bipartit, wenn er keinen <a href="Kreis_(Graphentheorie)" class="mw-redirect" title="Kreis (Graphentheorie)">Kreis</a> ungerader Länge enthält.</li>

<li>Die <a href="Kantenchromatische_Zahl" class="mw-redirect" title="Kantenchromatische Zahl">kantenchromatische Zahl</a> entspricht seinem <a href="Maximalgrad" class="mw-redirect" title="Maximalgrad">Maximalgrad</a>.</li>

<li>Der <a href="Listenchromatischer_Index" class="mw-redirect" title="Listenchromatischer Index">Listenchromatische Index</a> ist gleich dem <a href="Chromatischer_Index" class="mw-redirect" title="Chromatischer Index">chromatischen Index</a>. Damit sind bipartite Graphen eine Klasse von Graphen, für welche die <a href="Listenf%C3%A4rbung#Eigenschaften" title="Listenfärbung">Listenfärbungsvermutung</a> zutrifft.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{T}(G)\leq \Delta (G)+2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fa15f4e35bde30c9b82657ef53c2751993db02b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.154ex; height:2.843ex;" alt="{\displaystyle \chi _{T}(G)\leq \Delta (G)+2}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{T}(G)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{T}(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3633659b68814979ded1fa662444312e9eddd313.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.48ex; height:2.843ex;" alt="{\displaystyle \chi _{T}(G)}" loading="lazy"> die <a href="Totalchromatische_Zahl" class="mw-redirect" title="Totalchromatische Zahl">totalchromatische Zahl</a> ist und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/359a5b6529b6b451a49a95beec7c87d147f51961.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.572ex; height:2.843ex;" alt="{\displaystyle \Delta (G)}" loading="lazy"> der <a href="Maximalgrad" class="mw-redirect" title="Maximalgrad">Maximalgrad</a>. Für bipartite Graphen gilt also die <a href="Totalf%C3%A4rbung" title="Totalfärbung">Totalfärbungsvermutung</a>.</li>

<li>Alle bipartiten Graphen sind <a href="Perfekter_Graph" title="Perfekter Graph">perfekte Graphen</a>, somit stimmt für jeden <a href="Induzierter_Teilgraph" class="mw-redirect" title="Induzierter Teilgraph">induzierten Teilgraphen</a> die <a href="Cliquenzahl" class="mw-redirect" title="Cliquenzahl">Cliquenzahl</a> mit der <a href="Chromatische_Zahl" title="Chromatische Zahl">chromatischen Zahl</a> überein.</li></ul>

Nach dem <a href="Satz_von_K%C3%B6nig_(Graphentheorie)" title="Satz von König (Graphentheorie)">Satz von König</a> entspricht in bipartiten Graphen die Größe der minimalen <a href="Knoten%C3%BCberdeckung" title="Knotenüberdeckung">Knotenüberdeckung</a> der Größe des <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">maximalen Matchings</a>. Eine alternative und äquivalente Form dieses Satzes besteht darin, dass die Größe der maximalen unabhängigen Menge plus die Größe des maximalen Matchings gleich der Anzahl der Knoten ist. In jedem <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> ohne isolierte <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> entspricht die Größe der minimalen <a href="Kanten%C3%BCberdeckung" class="mw-redirect" title="Kantenüberdeckung">Kantenüberdeckung</a> plus der Größe eines maximalen Matchings der Anzahl der Knoten. Aus der Kombination dieser Gleichung mit dem Satz von König folgt, dass in bipartiten Graphen die Größe der minimalen Kantenüberdeckung gleich der Größe der maximalen unabhängigen Menge ist und dass die Größe der minimalen Kantenüberdeckung plus der Größe der minimalen Knotenüberdeckung gleich der Anzahl der Knoten ist.

Außerdem gilt: Jeder bipartite Graph, das Komplement jedes bipartiten Graphen, der <a href="Kantengraph" title="Kantengraph">Kantengraph</a> jedes bipartiten Graphen und das Komplement des Kantengraphen jedes bipartiten Graphen sind alle <a href="Perfekter_Graph" title="Perfekter Graph">perfekte Graphen</a>. Dies war eines der Ergebnisse, die die Definition perfekter Graphen motivierten.<a href="#cite_note-1">[1]</a>

Nach dem Satz der starken perfekten Graphen haben die perfekten Graphen eine verbotene Charakterisierung, die der von bipartiten Graphen ähnelt: Ein Graph ist genau dann bipartit, wenn er keinen ungeraden Zyklus als <a href="Teilgraph" title="Teilgraph">Teilgraph</a> hat, und ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> ist genau dann perfekt, wenn er keinen ungerader <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a> oder sein <a href="Komplementgraph" title="Komplementgraph">Komplementgraphen</a> als induzierten Teilgraphen hat. Die bipartiten Graphen, <a href="Kantengraph" title="Kantengraph">Kantengraphen</a> von bipartiten Graphen und ihre Komplementgraphen bilden vier der fünf Grundklassen perfekter Graphen, die für den Beweis des Satzes der starken perfekten Graphen verwendet werden.<a href="#cite_note-2">[2]</a>

Für einen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> wird die Anzahl benachbarter Knoten als <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Grad</a> des Knoten bezeichnet und als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \deg(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \deg(v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ccd42aee2bfea48d98b03eb19ca4bd3731f43d6a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.424ex; height:2.843ex;" alt="{\displaystyle \deg(v)}" loading="lazy"> bezeichnet. Die Gradsummenformel für einen bipartiten Graphen besagt, dass

</mrow>

</munder>

</mrow>

</munder>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{v\in A}\deg(v)=\sum _{u\in B}\deg(u)=|E|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41a934da19b8fc841714b9f0816412a11862bf1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:29.801ex; height:5.676ex;" alt="{\displaystyle \sum _{v\in A}\deg(v)=\sum _{u\in B}\deg(u)=|E|}" loading="lazy"></dd></dl>

Die <a href="Gradfolge" title="Gradfolge">Gradfolge</a> eines bipartiten Graphen ist das Paar von Listen, das jeweils die <a href="Knotengrad" class="mw-redirect" title="Knotengrad">Knotengrade</a> der beiden Partitionsklassen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> enthält. Beispielsweise hat der vollständige bipartiten Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,5}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26040679270db13db94cd92b8bf581603edccc48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,5}}" loading="lazy"> die Gradfolge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (5,5,5),(3,3,3,3,3)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5,5,5),(3,3,3,3,3)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42552ff13646bc562427f9242a6d196a940c1818.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.156ex; height:2.843ex;" alt="{\displaystyle (5,5,5),(3,3,3,3,3)}" loading="lazy">. <a href="Isomorphismus" title="Isomorphismus">Isomorphe</a> bipartite Graphen haben die gleiche Gradfolge. Die Gradfolge identifiziert jedoch im Allgemeinen einen bipartiten Graphen nicht eindeutig. In einigen Fällen können nicht-isomorphe zweigliedrige Graphen die gleiche Gradfolge aufweisen.

<div class="mw-heading mw-heading2"><h2 id="Kombinatorik">Kombinatorik</h2></div>

Die Anzahl der bipartiten Graphen steigt schneller als <a href="Exponentialfunktion" title="Exponentialfunktion">exponentiell</a> mit der Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> der <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>. Die folgende <a href="Tabelle" title="Tabelle">Tabelle</a> zeigt die mit Hilfe eines <a href="Computer" title="Computer">Computers</a> bestimmten Anzahlen für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq 12}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq 12}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ced0c8199572399fda990e12bbbbc5192f3c0cae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.818ex; height:2.343ex;" alt="{\displaystyle n\leq 12}" loading="lazy">:<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a>

<th colspan="3">Anzahl der bipartiten Graphen

</th></tr>

<tr>

<th>n

</th>

<th>alle

</th>

<th>zusammenhängend

</th></tr>

<tr>

<th>1

</th>

<td>1

</td>

<td>1

</td></tr>

<tr>

<th>2

</th>

<td>2

</td>

<td>1

</td></tr>

<tr>

<th>3

</th>

<td>3

</td>

<td>1

</td></tr>

<tr>

<th>4

</th>

<td>7

</td>

<td>3

</td></tr>

<tr>

<th>5

</th>

<td>13

</td>

<td>5

</td></tr>

<tr>

<th>6

</th>

<td>35

</td>

<td>17

</td></tr>

<tr>

<th>7

</th>

<td>88

</td>

<td>44

</td></tr>

<tr>

<th>8

</th>

<td>303

</td>

<td>182

</td></tr>

<tr>

<th>9

</th>

<td>1119

</td>

<td>730

</td></tr>

<tr>

<th>10

</th>

<td>5479

</td>

<td>4032

</td></tr>

<tr>

<th>11

</th>

<td>32303

</td>

<td>25598

</td></tr>

<tr>

<th>12

</th>

<td>251135

</td>

<td>212780

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Algorithmen">Algorithmen</h2></div>

<div class="sieheauch" role="navigation" style="font-style:italic;">Siehe auch: <a href="Graphpartitionierung" title="Graphpartitionierung">Graphpartitionierung</a></div>

Mit dem <a href="Algorithmus_von_Hopcroft_und_Karp" title="Algorithmus von Hopcroft und Karp">Algorithmus von Hopcroft und Karp</a> lässt sich in der <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m{\sqrt {n}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m{\sqrt {n}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5245a222139778d01eafa6e99653ce6584c4e021.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.954ex; height:3.009ex;" alt="{\displaystyle O(m{\sqrt {n}})}" loading="lazy"> ein <a href="Maximales_Matching" class="mw-redirect" title="Maximales Matching">maximales Matching</a> finden und darüber auch die <a href="Stabilit%C3%A4tszahl" class="mw-redirect" title="Stabilitätszahl">Stabilitätszahl</a> bestimmen.

Mit einem einfachen <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der auf <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> basiert, lässt sich in linearer <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> bestimmen, ob ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> bipartit ist, und eine gültige Partition bzw. 2-<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">Färbung</a> ermitteln. Dabei wird einem beliebigen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> eine Farbe, und seinen Kindern die jeweils komplementäre Farbe zugewiesen. Wird beim Färben festgestellt, dass zwei benachbarte Knoten die gleiche Farbe haben, ist der Graph nicht bipartit.

Die Hauptidee besteht darin, jedem <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> die Farbe zuzuweisen, die sich von der Farbe des übergeordneten Knotens in der <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> unterscheidet, und Farben in der Hauptreihenfolge der Tiefensuche zuzuweisen. Dies führt zwangsläufig zu einer 2-<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">Färbung</a> des <a href="Aufspannender_Baum" class="mw-redirect" title="Aufspannender Baum">aufspannenden</a> Waldes, der aus den <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> besteht, die die Knoten mit ihren übergeordneten Knoten verbinden, aber möglicherweise werden einige Kanten, die nicht zum Wald gehören, nicht richtig gefärbt. Einer der beiden Endknoten jeder Kante, die nicht zum Wald gehört, ist ein Vorfahr des anderen Endknotens. Wenn bei der Tiefensuche eine Kante dieses Typs entdeckt wird, sollte überprüft werden, ob diese beiden Knoten unterschiedliche Farben haben. Wenn dies nicht der Fall ist, bildet der Pfad im Wald vom Vorfahren zum Nachkommen zusammen mit der falsch gefärbten Kante einen ungeraden <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a>, der vom <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zusammen mit dem Ergebnis zurückgegeben wird, dass der Graph nicht bipartit ist. Wenn der Algorithmus jedoch beendet wird, ohne einen ungeraden Zyklus dieses Typs zu finden, muss jede Kante richtig gefärbt sein, und der Algorithmus gibt die Färbung zusammen mit dem Ergebnis zurück, dass der Graph bipartit ist.<a href="#cite_note-5">[5]</a>

Alternativ kann ein ähnlicher <a href="Algorithmus" title="Algorithmus">Algorithmus</a> mit <a href="Breitensuche" title="Breitensuche">Breitensuche</a> anstelle der Tiefensuche verwendet werden. Wiederum erhält jeder <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> die entgegengesetzte Farbe zu seinem übergeordneten Knoten im <a href="Suchbaum" title="Suchbaum">Suchbaum</a> in der Reihenfolge der Breitensuche. Wenn beim Färben eines Knotens eine <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kante</a> vorhanden ist, die ihn mit einem zuvor gefärbten Knotens mit derselben Farbe verbindet, bildet diese Kante zusammen mit den <a href="Pfad_(Graphentheorie)" class="mw-redirect" title="Pfad (Graphentheorie)">Pfaden</a> im Suchbaum der Breitensuche ihrer beiden Endpunkte mit ihrem letzten gemeinsamen Vorfahren einen ungeraden <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a>. Wenn der Algorithmus beendet wird, ohne auf diese Weise einen ungeraden Zyklus zu finden, muss er eine korrekte Färbung gefunden haben und kann daraus schließen, dass der Graph bipartit ist.<a href="#cite_note-6">[6]</a>

Für die Schnittgraphen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Strecken oder andere einfache Formen in der <a href="Euklidische_Ebene" class="mw-redirect" title="Euklidische Ebene">euklidischen Ebene</a> ist es möglich, mit einer <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41addf5ff9fad19fe3a34d951c6ada35738b171f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.909ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n))}" loading="lazy"> zu testen, ob der <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> bipartit ist und entweder eine 2-<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">Färbung</a> oder einen ungeraden <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a> zu finden, obwohl der Graph selbst bis zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"> <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> haben kann.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="Matchings">Matchings</h3></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching (Graphentheorie)</a></div>Ein <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching</a> in einem <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> ist eine <a href="Teilmenge" title="Teilmenge">Teilmenge</a> seiner <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a>, von denen keine zwei einen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> gemeinsam haben. <a href="Algorithmus" title="Algorithmus">Algorithmen</a> mit <a href="Polynomieller_Algorithmus" class="mw-redirect" title="Polynomieller Algorithmus">polynomieller</a> <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> sind für viele Anwendungen mit Matchings bekannt, einschließlich <a href="Maximales_Matching" class="mw-redirect" title="Maximales Matching">maximaler Matchings</a>, dem Maximum Weight Matching und dem <a href="Stable_Marriage_Problem" title="Stable Marriage Problem">Stable Marriage Problem</a>.<a href="#cite_note-8">[8]</a>

In vielen Fällen sind Matching-Probleme für bipartite Graphen einfacher zu lösen als für nicht bipartite Graphen, und viele Matching-Algorithmen wie der <a href="Algorithmus_von_Hopcroft_und_Karp" title="Algorithmus von Hopcroft und Karp">Algorithmus von Hopcroft und Karp</a> für maximale Matchings funktionieren nur für bipartite Graphen korrekt.<a href="#cite_note-9">[9]</a>

Nehmen wir als einfaches Beispiel an, dass eine Gruppe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> von Personen Jobs aus einer Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/359e4f407b49910e02c27c2f52e87a36cd74c053.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.471ex; height:2.176ex;" alt="{\displaystyle J}" loading="lazy"> von Jobs sucht, wobei nicht alle Personen für alle Jobs geeignet sind. Diese Situation kann als bipartiter Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P,J,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (P,J,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/199b79f3770b422cc1d980e885a6e6dc66eea291.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.87ex; height:2.843ex;" alt="{\displaystyle (P,J,E)}" loading="lazy"> modelliert werden, bei dem eine Kante jeden Arbeitssuchenden mit jedem geeigneten Job verbindet. Ein <a href="Perfektes_Matching" class="mw-redirect" title="Perfektes Matching">perfektes Matching</a> beschreibt eine Möglichkeit, alle Arbeitssuchenden gleichzeitig zufrieden zu stellen und alle Jobs zu besetzen. Der <a href="Heiratssatz" title="Heiratssatz">Heiratssatz</a> liefert eine Charakterisierung der bipartiten Graphen, die ein perfektes Matching ermöglichen. Das <a href="National_Resident_Matching_Program" title="National Resident Matching Program">National Resident Matching Program</a> in den Vereinigten Staaten verwendet Matching-Algorithmen, um dieses Problem für Medizinstudenten und Jobs in Krankenhäusern zu lösen.

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerung">Verallgemeinerung</h2></div>

Ein <a href="K-partiter_Graph" title="K-partiter Graph">k-partiter Graph</a> ist ein Graph, dessen Knotenmenge in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Partitionen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten einer Partition gibt.

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a> zeigt die Implementierung eines <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der prüft, ob ein <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteter Graph</a> bipartit ist. Der ungerichtete Graph wird als <a href="Feld_(Datentyp)#Dimensionen" class="mw-redirect" title="Feld (Datentyp)">zweidimensionales Array</a> für die <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a> deklariert. Der Algorithmus weist <a href="Benachbart" class="mw-redirect" title="Benachbart">benachbarten</a> Knoten alternierende Farben zu. Bei der Ausführung des Programms wird die <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methode</a> Main verwendet, die das Ergebnis auf der Konsole ausgibt.<a href="#cite_note-10">[10]</a><div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>using System;

using System.Collections.Generic;

class BipartiteGraph

{

// Diese Methode gibt true zurück, wenn der Graph bipartit ist, sonst false. Benachbarten Knoten werden alternierende Farben zugewiesen.

private static bool IsBipartite(int[,] graph, int startIndex, int[] coloredVertices)

{

coloredVertices[startIndex] = 1; // Weist dem Startknoten eine Farbe zu

Queue<int> queue = new Queue<int>(); // Deklariert eine Queue für die Knotenindexe

queue.Enqueue(startIndex); // Fügt den Startknoten der Queue hinzu

while (queue.Count != 0) // Solange die Queue nicht leer ist

{

int index = queue.Peek(); // Index des vordersten Knotens

queue.Dequeue(); // Entfernt den vordersten Knoten

{

return false;

}

for (int i = 0; i < coloredVertices.Length; i++) // for-Schleife, die die Knoten durchläuft

{

if (graph[index, i] == 1 && coloredVertices[i] == -1) // Wenn die Knoten verbunden sind und der Zielknoten nicht gefärbt ist

{

coloredVertices[i] = 1 - coloredVertices[index]; // Weist dem benachbarten Knoten die alternierende Farbe zu

queue.Enqueue(i); // Fügt den Knoten der Queue hinzu

}

else

{

if (graph[index, i] == 1 && coloredVertices[i] == coloredVertices[index]) // Wenn die Knoten verbunden sind und dieselbe Farbe haben, wird false zurückgegeben

{

return false;

}

return true; // Wenn alle benachbarten Knoten alternierende Farben haben, wird true zurückgegeben

}

// Diese Methode gibt true zurück, wenn der Graph bipartit ist, sonst false

{

int[] coloredVertices = new int[numberOfVertices]; // Deklariert ein Array für die Farben der Knoten

for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die die Knoten durchläuft

{

coloredVertices[i] = -1; // Initialisiert die Knoten mit -1, sodass die Knoten am Anfang nicht gefärbt sind

}

// Prüfung für die Komponenten des Graphen

for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die die Knoten durchläuft

{

if (coloredVertices[i] == -1 && !IsBipartite(graph, i, coloredVertices)) // Wenn der Knoten noch nicht gefärbt ist und die Komponente mit diesem Startknoten nicht bipartit ist, wird false zurückgegeben

{

return false;

}

return true; // Wenn alle Komponenten bipartit sind, wird true zurückgegeben

}

// Hauptmethode, die das Programm ausführt

public static void Main(String[] args)

{

// Deklariert und initialisiert ein zweidimensionales Array für die Adjazenzmatrix eines ungerichteten Graphen mit 4 Knoten

int[,] graph = {{ 0, 1, 0, 1 },

{1, 0, 1, 0},

{0, 1, 0, 1},

};

int numberOfVertices = (int) graph.GetLongLength(0); // Variable für die Anzahl der Knoten

if (IsBipartite(graph, numberOfVertices)) // Aufruf der Methode

{

Console.WriteLine("Der Graph ist bipartit."); // Ausgabe auf der Konsole

}

else

{

Console.WriteLine("Der Graph ist nicht bipartit."); // Ausgabe auf der Konsole

}

Console.ReadLine();

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching (Graphentheorie)</a></li>

<li><a href="Petri-Netz" title="Petri-Netz">Petri-Netz</a></li>

<li><a href="Sekret%C3%A4rinnenproblem" title="Sekretärinnenproblem">Sekretärinnenproblem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1.</li>

<li>Sven Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen, Vieweg+Teubner Verlag, 2012, ISBN 978-3-8348-1849-2.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikiversity.org/wiki/Kurs:Diskrete_Mathematik_(Osnabr%C3%BCck_2020)/Vorlesung_20" class="extiw external" title="v:Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 20">Wikiversity: Eine Vorlesung über bipartite Graphen im Rahmen eines Kurses zur diskreten Mathematik</a> – Kursmaterialien</div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Bipartite_graphs?uselang=de">Commons: Bipartiter Graph</a> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li><a rel="nofollow" class="external text" href="https://www.spektrum.de/lexikon/mathematik/bipartiter-graph/2289">Bipartiter Graph.</a> In: Springer Lexikon der Mathematik.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Béla Bollobás: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Modern Graph Theory</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Graduate Texts in Mathematics</cite>. 184. Jahrgang. Springer, 1998 (englisch, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165">google.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=Modern+Graph+Theory&rft.au=B%C3%A9la+Bollob%C3%A1s&rft.btitle=Graduate+Texts+in+Mathematics&rft.date=1998&rft.genre=book&rft.pub=Springer&rft.volume=184.+Jahrgang" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The strong perfect graph theorem</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></cite>. 164. Jahrgang, Nr. 1, 2006, S. 51–229, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4007/annals.2006.164.51">10.4007/annals.2006.164.51</a>, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0212070">math/0212070</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=The+strong+perfect+graph+theorem&rft.au=Maria%26%2332%3BChudnovsky%2C%26%2332%3BNeil%26%2332%3BRobertson%2C%26%2332%3BPaul%26%2332%3BSeymour%2C+...&rft.date=2006&rft.doi=10.4007%2Fannals.2006.164.51&rft.genre=journal&rft.issue=1&rft.jtitle=Annals+of+Mathematics&rft.pages=51-229&rft.volume=164.+Jahrgang" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Folge <a href="https://oeis.org/A033995" class="extiw external" title="oeis:A033995">A033995</a> in <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Folge <a href="https://oeis.org/A005142" class="extiw external" title="oeis:A005142">A005142</a> in <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> Robert Sedgewick: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Algorithms in Java, Part 5: Graph Algorithms</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Addison-Wesley</cite>. 2004, S. 109–111 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=Algorithms+in+Java%2C+Part+5%3A+Graph+Algorithms&rft.au=Robert%26%2332%3BSedgewick&rft.btitle=Addison-Wesley&rft.date=2004&rft.genre=book&rft.pages=109-111" style="display:none">

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Jon Kleinberg, Éva Tardos: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Algorithm Design</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Addison-Wesley</cite>. 2006, S. 94–97 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=Algorithm+Design&rft.au=Jon%26%2332%3BKleinberg%2C%26%2332%3B%C3%89va%26%2332%3BTardos&rft.btitle=Addison-Wesley&rft.date=2006&rft.genre=book&rft.pages=94-97" style="display:none">

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> David Eppstein: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Testing bipartiteness of geometric intersection graphs</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">ACM Transactions on Algorithms</cite>. 5. Jahrgang, Nr. 2, 2009, S. Art. 15, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145/1497290.1497291">10.1145/1497290.1497291</a>, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs.CG/0307023">cs.CG/0307023</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=Testing+bipartiteness+of+geometric+intersection+graphs&rft.au=David%26%2332%3BEppstein&rft.date=2009&rft.doi=10.1145%2F1497290.1497291&rft.genre=journal&rft.issue=2&rft.jtitle=ACM+Transactions+on+Algorithms&rft.pages=Art.+15&rft.volume=5.+Jahrgang" style="display:none">

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Network Flows: Theory, Algorithms, and Applications</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Prentice Hall</cite>. 1993, S. 461–509 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=Network+Flows%3A+Theory%2C+Algorithms%2C+and+Applications&rft.au=Ravindra+K.%26%2332%3BAhuja%2C%26%2332%3BThomas+L.%26%2332%3BMagnanti%2C%26%2332%3BJames+B.%26%2332%3BOrlin&rft.btitle=Prentice+Hall&rft.date=1993&rft.genre=book&rft.pages=461-509" style="display:none">

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> John E. Hopcroft, Richard M. Karp: <cite class="lang" lang="en" dir="auto" style="font-style:italic">An n5/2 algorithm for maximum matchings in bipartite graphs</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">SIAM Journal on Computing</cite>. 2. Jahrgang, Nr. 4, 1973, S. 225–231, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137/0202019">10.1137/0202019</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Bipartiter+Graph&rft.atitle=An+n5%2F2+algorithm+for+maximum+matchings+in+bipartite+graphs&rft.au=John+E.%26%2332%3BHopcroft%2C%26%2332%3BRichard+M.%26%2332%3BKarp&rft.date=1973&rft.doi=10.1137%2F0202019&rft.genre=journal&rft.issue=4&rft.jtitle=SIAM+Journal+on+Computing&rft.pages=225-231&rft.volume=2.+Jahrgang" style="display:none">

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/bipartite-graph/">Check whether a given graph is Bipartite or not</a>

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4145661-0">4145661-0</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-19" href="https://de.wikipedia.org/wiki/?title=Bipartiter_Graph&oldid=260742696">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>